package com.xxwy.lintcode;

/**
 * @author xxwy
 * on 2018/10/10 0010
 * Unique Paths
 */
public class Num115 {

    public int uniquePathsWithObstacles(int[][] A) {
        // write your code here

        int m = A.length;
        int n = A[0].length;
        if (m == 0 || n == 0 || A[0][0] == 1 || A[m - 1][n - 1] == 1) {
            return 0;
        }
        int[][] f = new int[m][n];
        f[0][0] = 1;
        int i, j;
        //行
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    f[i][j] = 0;
                    continue;
                }
                if (i == 0 && j >= 1 && f[0][j - 1] != 0) {
                    f[i][j] = 1;
                    continue;
                }
                if (j == 0 && i >= 1 && f[i-1][0] != 0) {
                    f[i][j] = 1;
                    continue;
                }
                if (j != 0 && i != 0) {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
            return f[m - 1][n - 1];

        }
    }
